class Solution {
public:
    vector<string> split(string& str, char ch)
    {
        int pos = 0;
        int start = 0;
        string s(str);
        vector<string> ret;

        while(pos < s.size())
        {
            while(pos < s.size() && s[pos] == ch)
            {
                pos++;
            }
            start = pos;

            while(pos < s.size() && s[pos] != ch)
            {
                pos++;
            }

            //切割字典
            if(start < s.size())
            {
                ret.emplace_back(s.substr(start, pos - start));
            }
        }

        return ret;
    }

    string replaceWords(vector<string>& dictionary, string sentence) 
    {
        //构建哈希集合，方便快速查找
        unordered_set<string> dictionarySet;
        for(auto& s: dictionary)
        {
            dictionarySet.insert(s);
        }
        
        //将sentence切割成一个个的子串
        vector<string> words = split(sentence, ' ');

        for(auto& word : words)
        {
            for(int j = 0; j < word.size(); j++)
            {
                //找到字典结合前缀一样的词根进行替换
                if(dictionarySet.count(word.substr(0, 1 + j)))
                {
                    word = word.substr(0, 1 + j);
                    break;
                }
            }
        }

        string ret;

        for(int i = 0; i < words.size() - 1; i++)
        {
            ret.append(words[i]);
            ret.append(" ");
        }

        ret.append(words.back());

        return ret;
    }
};

#include <unistd.h>
class Solution {
public:
    int m,n;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
    bool visi[1010][1010] = {false};

    int rotApple(vector<vector<int> >& grid) 
    {
        m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        int ret = 0;
        
        //遍历原数组，将腐烂苹果入队列
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] == 2)
                    q.push({i, j});
        
        //多源bfs
        while (q.size()) 
        {
            int sz = q.size();
            ret++;
            while(sz--)
            {
                auto [a, b] = q.front();
                q.pop();
                for(int i = 0; i < 4; i++)
                {
                    int x = dx[i] + a, y = dy[i] + b;
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !visi[x][y])
                    {
                        visi[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }

        //遍历原数组，判断是否有未腐烂苹果
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)  
                if(!visi[i][j] && grid[i][j] == 1)
                    return -1;

        return ret - 1;       
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int LastRemaining_Solution(int n, int m) {
        if(n == 0) 
            return -1; // 处理边界情况
        vector<int>arr(n, 0);
        int n_count = 0;
        int m_count = 0;
        while(n_count < n - 1)
        {
            for(int i = 0; i < n; i++)
            {
                if(arr[i] == 0)
                    m_count++;
                if(m_count == m)
                {
                    arr[i] = 1;
                    m_count = 0;
                    n_count++;
                }
            }
        }
        auto iter = find(arr.begin(), arr.end(), 0);
        return iter- arr.begin();
    }
};

int LastRemaining_Solution(int n, int m) 
    {
        int f = 0;
        for(int i = 1; i <= n; i++)
        {
            f = (f + m) % i; // dp
        }
        return f;
    }

    string solve(string s, string t) 
    {
        string ret; 
        int i = s.size() - 1 , j = t.size() - 1;
        int tmp = 0;
        while(i >= 0 || j >= 0 || tmp)
        {
            if(j >= 0) tmp = t[j--] - '0' + tmp;
            if(i >= 0) tmp = s[i--] - '0' + tmp;
            ret += to_string(tmp % 10);
            tmp /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }

    class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 第一个整数
     * @param t string字符串 第二个整数
     * @return string字符串
     */
    string solve(string s, string t) 
    {
        //逆序字符串
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());

        int m = s.size(), n = t.size();
        vector<int> tmp(n + m);

        //  无进位相乘再相加
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                tmp[i + j] += (s[i] - '0') * (t[j] - '0');
        
        //进位加法
        string ret;
        int c = 0;
        for(int x : tmp)
        {
            c += x;
            ret += c % 10 + '0';
            c /= 10;
        }
        
        while(c)
        {
            ret += c % 10 + '0';
            c /= 10;
        }

        //去除前导0
        while(ret.size() > 1 && ret.back() == '0')
            ret.pop_back();
        
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) 
    {
        //处理边界情况
        if(head == nullptr)
            return nullptr;
        //创建虚拟头节点
        ListNode* guard = new ListNode;
        guard->next = head;

        //初始化对应节点值
        ListNode* prev = guard; 
        ListNode* cur = head;
        ListNode* next=nullptr,*nnext = nullptr;
        if(cur->next != nullptr)
        {
            next =cur->next;
            if(next) //nullptr不需要逆置
                nnext = next->next;
        }
        // prev -> cur -> next -> nnext
        while(cur && next)
        {
            // prev -> next -> cur -> nnext
            prev->next = next; 
            cur->next = nnext;
            next->next =cur;

            //迭代
            prev = cur;
            cur = nnext;
            if(cur != nullptr)
            {
                next = cur->next;
                if(next)
                nnext = next->next;
            }
        }

        //处理动态申请内存
        cur = guard->next;
        delete guard;
        return cur;
    }
};

class Solution {
public:
    double myPow(double x, long long n)
    {
        //边界情况
        if(n == 0)
            return 1.0;

        //处理小于0的情况
        if(n < 0)
            return 1.0 / myPow(x, -n);

        //递归入口
        double tmp = myPow(x, n / 2);
        //需要考虑n是奇数还是偶数
        return n % 2 == 0 ? tmp*tmp : tmp*tmp*x;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    bool dfs(TreeNode* root)
    {
        //递归出口，当遍历到叶子节点返回
        if(root->left == nullptr)
            return root->val == 0 ? false : true;
        
        //根据左右子树的值进行计算
        bool left = dfs(root->left);
        bool right = dfs(root->right);
        if(root->val == 2)
        {
            return left | right;
        }
        
        return right & left;
    }

    bool evaluateTree(TreeNode* root) 
    {
        if(root->left == nullptr)
            return root->val == 0 ? false : true;

        return dfs(root);     
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        //排序，有序数组方便去重
        sort(nums.begin(),nums.end());

        int n = nums.size();
        vector<vector<int>> ret;

        for(int i = 0; i < n; )//从头开始固定一个数a
        {
            if(nums[i] >= 0) //当固定的数大于0，则不需要再找
                break;
            
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right)
            {
                if(nums[left] + nums[right] > target) right--;
                else if(nums[left] + nums[right] < target) left++;
                else ret.push_back({nums[i], nums[left], nums[right]});//此时结果符合三数之和
                //去重 left 和 right
                while(left < n && nums[left-1] == nums[left]) 
                    left++;
                while(right > i && nums[right] == nums[right+1]) 
                    right--;
            }
            i++;
            // 去重i
            while(i < n && nums[i] == nums[i+1])
                i++;
        } 

        return ret;
    }
};